|
課程名稱 |
資料結構與演算法實務
Practical Data Structures and Algorithms |
|
開課學期 |
100-2 |
|
授課對象 |
生命科學院 基因體與系統生物學學位學程 |
|
授課教師 |
陳倩瑜 |
|
課號 |
BME5010 |
|
課程識別碼 |
631 U1260 |
|
班次 |
|
|
學分 |
3 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期二5,6(12:20~14:10)星期四5(12:20~13:10) |
|
上課地點 |
知201知201 |
|
備註 |
總人數上限：30人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1002DSAP |
|
課程簡介影片 |
|
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
此一課程在於介紹多種常用之資料結構與相關演算法，增進修課學生的程式設計能力，以期未來能在不同領域實際應用。
每週課程計畫進度：
1. Complexity
2. Linear Lists – Array Representation
3. Linear Lists – Linked Representation
4. Arrays and Matrices
5. Stacks
6. Queues
7. Skip Lists and Hashing
8. Binary and Other Trees
9. Priority Queues
10. Greedy Method
11. Divide and Conquer
12. Dynamic Programming
13. Backtracking
14. Branch and Bound
|
|
課程目標 |
本課程將搭配C++程式編輯，介紹多種可使用的資料結構，引領學生了解現有演算法，解決實際問題。 |
|
課程要求 |
修過至少一種基本程式設計課程(any language is fine, ext. C, C++, Java, Perl, ...) |
|
預期每週課後學習時數 |
|
|
Office Hours |
|
|
指定閱讀 |
|
|
參考書目 |
1. Robert Sedgewick, Algorithms in C++, Parts 1-4: Fundamentals, Data
Structure, Sorting, Searching (3rd Edition), Addison-Wesley Professional,
1998.
[http://my.safaribooksonline.com/book/programming/cplusplus/9780768685336]
2. Elliot B. Koffman and Paul A. T. Wolfgang, Objects, Abstraction, Data
Structures and Design: Using C++, Wiley, 2005.
3. Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani, Algorithms,
McGraw-Hill, 2006. (http://www.cs.berkeley.edu/~vazirani/algorithms.html) |
|
評量方式
(僅供參考) |
|
No. |
項目 |
百分比 |
說明 |
|
1. |
作業 |
40% |
約有十次寫程式的作業(使用c/c++) |
2. |
期中考 |
30% |
|
3. |
期末考 |
30% |
|
|
|
週次 |
日期 |
單元主題 |
|
第1週 |
02/21, 02/23 |
Introduction / connectivity problem (HW0) |
|
第2週 |
02/28, 03/01 |
[02/28 國定假日] Connectivity / time analysis |
|
第3週 |
03/06, 03/08 |
Complexity of algorithms (HW1: connectivity) |
|
第4週 |
03/13, 03/15 |
Recurrences / examples of algorithm analysis (HW2: algorithm analysis) |
|
第5週 |
03/20, 03/22 |
Arrays, linked lists, memory allocation, strings (HW3: vector and list) |
|
第6週 |
03/27, 03/29 |
Lists, stack, queues |
|
第7週 |
04/03, 04/05 |
溫書假 |
|
第8週 |
04/10, 04/12 |
ADT, stack (HW4-1: stack) |
|
第9週 |
04/17, 04/19 |
ADT / Recursion (HW4-2: recurrence) |
|
第10週 |
04/24, 04/26 |
Divide and Conquer, Dynamic programming (HW5: DP) |
|
第11週 |
05/01, 05/03 |
[05/01 期中考] [05/03 休息一次] |
|
第12週 |
05/08, 05/10 |
Tree Traversal, Recursion (HW6: construct and traverse trees) |
|
第13週 |
05/15, 05/17 |
Graphs and graph traversal |
|
第14週 |
05/22, 05/24 |
Paths in graphs (HW8: graph traversal) |
|
第15週 |
05/29, 05/31 |
Sorting |
|
第16週 |
06/05, 06/07 |
Priority queue and heapsort (HW9: shortest path) |
|
第17週 |
06/12, 06/14 |
Greedy Algorithms, Minimum Spanning Trees (HW10: MST) |
|
第18週 |
06/19, 06/21 |
[06/19 期末考 12:30pm開始] [06/21 無課程] |
|